// PrintPath.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>
#include <stack>
#include <queue>
#include <deque>
using namespace std;

#define null 0
struct TreeNode
{
    int value;
    TreeNode *left, *right;

    TreeNode() { };

    TreeNode(int v)
    {
        value=v;
        left=right=null;
    };
};

// Given a BST and two nodes' value on the tree, print the "UP", "LEFT" or "RIGHT" from s to t:
//   If it goes up, print "UP"
//   If it goes down to left child, print "LEFT"
//   If it goes down to right child, print "RIGHT"
//
// Algorithm:
//   1. First, find the lowest common ancester. Using two double-ended queues to save the path from root to s and t.
//   2. From s to the lowest common ancester, output "UP"
//   3. From the lowest common ancester to t, output "LEFT" or "RIGHT"
// Analysis:
//   Time Complexity: O(logn)
//   Space Complexity: O(logn)

bool FindNode(TreeNode *root,int value,deque<TreeNode *> &q)
{
    if(!root) return false;
    q.push_back(root);
    if(value<root->value && !FindNode(root->left,value,q) || value>root->value && !FindNode(root->right,value,q))
    {
        q.clear();
        return false;
    }
    else return true;
}

void PrintPath(TreeNode *root,int s,int t)
{
    if(!root||s>=t) return;

    deque<TreeNode *> q1,q2;
    if(!FindNode(root,s,q1)||!FindNode(root,t,q2)) return;

    TreeNode *ancester=null;
    while(!q1.empty()&&!q2.empty()&&q1.front()==q2.front())
    {
        ancester=q1.front();
        q1.pop_front();
        q2.pop_front();
    }

    while(!q1.empty())
    {
        cout<<"UP"<<" ";
        q1.pop_back();
    }

    while(!q2.empty())
    {
        if(ancester->left==q2.front()) cout<<"LEFT"<<" ";
        else cout<<"RIGHT"<<" ";
        ancester=q2.front();
        q2.pop_front();
    }  
}

int _tmain(int argc, _TCHAR* argv[])
{
    return 0;
}